package main

import (
	"math/rand"
)

func main() {
	c := Constructor()
	c.Insert(1)
	c.Insert(1)

}

/*
设计一个支持在平均 时间复杂度 O(1) 下， 执行以下操作的数据结构。
注意: 允许出现重复元素。
insert(val)：向集合中插入元素 val。
remove(val)：当 val 存在时，从集合中移除一个 val。
getRandom：从现有集合中随机获取一个元素。每个元素被返回的概率应该与其在集合中的数量呈线性相关。
示例:
// 初始化一个空的集合。
RandomizedCollection collection = new RandomizedCollection();
// 向集合中插入 1 。返回 true 表示集合不包含 1 。
collection.insert(1);
// 向集合中插入另一个 1 。返回 false 表示集合包含 1 。集合现在包含 [1,1] 。
collection.insert(1);
// 向集合中插入 2 ，返回 true 。集合现在包含 [1,1,2] 。
collection.insert(2);
// getRandom 应当有 2/3 的概率返回 1 ，1/3 的概率返回 2 。
collection.getRandom();
// 从集合中删除 1 ，返回 true 。集合现在包含 [1,2] 。
collection.remove(1);
// getRandom 应有相同概率返回 1 和 2 。
collection.getRandom();
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/insert-delete-getrandom-o1-duplicates-allowed
*/

type RandomizedCollection struct {
	set         map[int]*Node
	data        []int
	length      int
}
type Node struct {
	val         int
	next        *Node
}

/** Initialize your data structure here. */
func Constructor() RandomizedCollection {

	return RandomizedCollection{make(map[int]*Node), make([]int, 0, 100), 0}
}


/** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
func (this *RandomizedCollection) Insert(val int) bool {
	res := false
	if _, ok := this.set[val]; !ok {
		res = true
	}
	this.data = append(this.data, val)
	newNode := &Node{this.length, this.set[val]}
	this.set[val] = newNode
	this.length++
	return res
}


/** Removes a value from the collection. Returns true if the collection contained the specified element. */
func (this *RandomizedCollection) Remove(val int) bool {
	if _, ok := this.set[val]; ok {
		index := this.set[val].val
		last_val := this.data[len(this.data)-1]
		this.data[index] = last_val
		this.set[last_val].val = index
		if this.set[last_val].next != nil && this.set[last_val].next.val >  this.set[last_val].val{
			this.set[last_val].next.val, this.set[last_val].val = this.set[last_val].val, this.set[last_val].next.val
		}
		this.data = this.data[:len(this.data)-1]
		this.set[val] = this.set[val].next
		if this.set[val] == nil {
			delete(this.set, val)
		}
		this.length--
		return true
	}
	return false
}


/** Get a random element from the collection. */
func (this *RandomizedCollection) GetRandom() int {
	if this.length > 0 {
		index := rand.Intn(this.length)
		return this.data[index]
	}
	return -1
}

